#include <iostream>

using namespace std;

// 3. Longest Substring Without Repeating Characters
// https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
//
// 课程问答区 @yatkun 提出的方法,
// l每次可以向前跳跃, 而不仅仅是+1
// 但代价是, 为了获得这个跳跃的位置, 每次需要遍历整个窗口的字符串
//
// 时间复杂度: O(len(s)*len(charset))
// 空间复杂度: O(1)
class Solution
{
private:
    // 查看s[l...r-1]之间是否存在s[r]
    // 若存在,返回相应的索引, 否则返回-1
    int isDuplicateChar(const string &s, int l, int r)
    {
        for (int i = l; i < r; i++)
            if (s[i] == s[r])
                return i;
        return -1;
    }

public:
    int lengthOfLongestSubstring(string s)
    {

        int l = 0, r = 0; // 滑动窗口为s[l...r]
        int res = 0;

        // 在这里, 循环中止的条件可以是r + 1 < s.size(), 想想看为什么?
        while (r < s.size())
        {
            int index = isDuplicateChar(s, l, r);

            // 如果s[r]之前出现过
            // l可以直接跳到s[r+1]之前出现的位置 + 1的地方
            if (index != -1)
                l = index + 1;
            
            res = max(res, r - l + 1);
            r++;
        }
        return res;
    }
};

int main()
{
    cout << Solution().lengthOfLongestSubstring("abcabcbb") << endl; // 3
    cout << Solution().lengthOfLongestSubstring("bbbbb") << endl;    // 1
    cout << Solution().lengthOfLongestSubstring("pwwkew") << endl;   // 3
    cout << Solution().lengthOfLongestSubstring("c") << endl;        // 1
    cout << Solution().lengthOfLongestSubstring("") << endl;         // 0

    return 0;
}